﻿/** 
 * Copyright (c) 2001 University of Maryland, College Park, MD 20742, USA
 * Copyright (c) 2005 In4Arch
 *
 *  The MIT License
 *  Permission is hereby granted, free of charge, to any person obtaining a copy of this 
 *  software and associated documentation files (the "Software"), to deal in the Software 
 *  without restriction, including without limitation the rights to use, copy, modify, merge, 
 *  publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons 
 *  to whom the Software is furnished to do so, subject to the following conditions:
 *
 *  The above copyright notice and this permission notice shall be included in all copies 
 *  or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
 *  INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A 
 *  PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 
 *  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF 
 *  CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE 
 *  OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 * Authors: Benjamin B. Bederson and Martin Wattenberg 2001 
 * http://www.cs.umd.edu/hcil/treemap-history/index.shtml
 * 
 * Author: moedusa moedusa@gmail.com 2005
 * http://moedusa.name/
 *
 * Author: Nikita Shlyakhov shlyakhov@mail.ru 2006
 **/
 
import in4arch.alg.treemap.AbstractMapLayout; 
import in4arch.alg.treemap.SliceLayout; 
import in4arch.alg.treemap.MapModel; 
import in4arch.alg.treemap.Mappable; 
import in4arch.alg.treemap.Rect; 

/**
 * "Squarified" treemap layout invented by
 * J.J. van Wijk.
 */
class in4arch.alg.treemap.SquarifiedLayout extends AbstractMapLayout {
	
    public function layout(model:MapModel, bounds:Rect):Void {
		var items_array:Array = model.getItems();
		items_array = sortDescending(items_array);
		_layout(items_array, 0, items_array.length-1, bounds);
	}
	
    public function _layout(items_array:Array, startIndex:Number, stopIndex:Number, bounds:Rect):Void {
        if (startIndex > stopIndex) {
			throw new Error("No layout since start("+startIndex+") > stop("+stopIndex+")");
		}
		
        if (stopIndex - startIndex < 2) {
            layoutBest(items_array, startIndex, stopIndex, bounds);
            return;
        }
	
        var x:Number = bounds.x;
		var y:Number = bounds.y; 
		var w:Number = bounds.w;
		var h:Number = bounds.h;
		
        var total:Number = sum(items_array, startIndex, stopIndex);
        var mid:Number = startIndex;
        var a:Number = items_array[startIndex].getSize()/total;
        var b:Number = a;
		
        if (w < h) {
            // height/width
            while (mid <= stopIndex) {
                var aspect:Number = normAspect(h,w,a,b);
                var q:Number=items_array[mid].getSize()/total;
				var naspect:Number = normAspect(h,w,a,b+q);
                if (naspect > aspect){
					break;
				}
                mid++;
                b+=q;
            }
            layoutBest(items_array, startIndex, mid, new Rect(x, y, w, h*b));
            _layout(items_array, mid+1, stopIndex, new Rect(x, y+h*b, w, h*(1-b)));
		
        } else {
			
            // width/height
            while (mid <= stopIndex) {
                var aspect:Number = normAspect(w,h,a,b);
                var q:Number = items_array[mid].getSize()/total;
				var naspect:Number = normAspect(w,h,a,b+q);				
                if (naspect > aspect){
					break;
				}
                mid++;
                b+=q;
            }
            layoutBest(items_array, startIndex, mid, new Rect(x, y, w*b, h));
            _layout(items_array, mid+1, stopIndex, new Rect(x+w*b, y, w*(1-b), h));
        }		
		
    }
    
    private function aspect(big:Number, small:Number, a:Number, b:Number):Number {
        return (big*b)/(small*a/b);
    }
	
    private function normAspect(big:Number, small:Number, a:Number, b:Number):Number {
        var x:Number = aspect(big,small,a,b);
        if (x<1) {
			// ?
		 return 1/x;
		}
        return x;
    }
	
    private function sum(items_array:Array, startIndex:Number, stopIndex:Number):Number    {
        var s:Number = 0;
        for (var i = startIndex; i <= stopIndex; i++) {
            s += items_array[i].getSize();
		}
        return s;
    }
    
    public function getName():String {
        return "Squarified";
    }
    
    public function getDescription():String {
        return "Algorithm used by J.J. van Wijk.";
    }
	
	/*
	private function layoutBest(items_array:Array, startIndex:Number, stopIndex:Number, bounds:Rect):Void {
		var ornt:Number = bounds.w > bounds.h ? AbstractMapLayout.HORIZONTAL : AbstractMapLayout.VERTICAL;
        sliceLayout(items_array, startIndex, stopIndex, bounds, ornt, AbstractMapLayout.ASCENDING);
    }
	*/
}